package com.zp.self.module.level_4_算法练习.数据结构.栈与队列;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author By ZengPeng
 */
public class 力扣_496_下一个更大元素I {
    //测试
    public static void main(String[] args) {

        int[] ints = new 力扣_496_下一个更大元素I().nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]+",");
        }

        System.out.println();

        ints = new 力扣_496_下一个更大元素I().nextGreaterElement(new int[]{2,4}, new int[]{1,2,3,4});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]+",");
        }

        System.out.println();

        ints = new 力扣_496_下一个更大元素I().nextGreaterElement(new int[]{1,3,5,2,4}, new int[]{6,5,4,3,2,1,7});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]+",");
        }
    }

    /*
    题目：nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
        给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
        对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
        返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

        示例 1：
        输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
        输出：[-1,3,-1]
        解释：nums1 中每个值的下一个更大元素如下所述：
        - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
        - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
        - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

        示例 2：
        输入：nums1 = [2,4], nums2 = [1,2,3,4].
        输出：[3,-1]
        解释：nums1 中每个值的下一个更大元素如下所述：
        - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
        - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

        进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

    分析：【Good】
        1.常规遍历
       *.从后向前遍历nums2,HashMap存储每个数字的下一个最大值 【有缺陷：不能找到右边最近的】
       大神:栈还能这样用 ,佩服??

    边界值 & 注意点：
       1.
    */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack =new Stack<>();
        stack.push(nums2[0]);
        for (int i = 1; i < nums2.length; i++) {
            while (!stack.isEmpty()){
                if(stack.peek()<nums2[i]){
                    map.put(stack.pop(),nums2[i]);
                }else break;
            }
            stack.push(nums2[i]);
        }
        while (!stack.isEmpty())
            map.put(stack.pop(),-1);
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++)
            res[i] = map.get(nums1[i]);
        return res;
    }
}
